#include <bits/stdc++.h>

using namespace std;

// 快速获得数据流的中位数的结构
// 测试链接 : https://leetcode.cn/problems/find-median-from-data-stream/

// 对顶堆帖子：https://oi-wiki.org/ds/binary-heap/
// 加餐链接：
class MedianFinder 
{
private:
    priority_queue<int, vector<int>, less<int>> maxHeap;
    priority_queue<int, vector<int>, greater<int>> minHeap;

    void balance()
    {
        int gap = maxHeap.size() - minHeap.size();
        // 两个堆元素个数的差值只能小于等于 1
        if(abs(gap) == 2)
        {
            if(maxHeap.size() > minHeap.size())
            {
                minHeap.emplace(maxHeap.top());
                maxHeap.pop();
            }
            else
            {
                maxHeap.emplace(minHeap.top());
                minHeap.pop();
            }
        }
    }

public:
    MedianFinder() 
    {}
    
    void addNum(int num) 
    {
        if(maxHeap.empty() || maxHeap.top() >= num)
            maxHeap.emplace(num);
        else
            minHeap.emplace(num);
        
        balance();
    }
    
    double findMedian() 
    {
        if(maxHeap.size() == minHeap.size())
            return (maxHeap.top() + minHeap.top()) / 2.0;
        else 
            return maxHeap.size() > minHeap.size() ? maxHeap.top() : minHeap.top();
    }
};